1534. Делимость
Имеется набор
целых чисел a1, a2,
..., an. Определите
количество чисел в диапазоне от l до r включительно, которые делятся
хотя бы на одно число из данного набора.
Вход. Состоит из нескольких тестов.
Первая строка каждого теста содержит два целых числа l (1 ≤ l ≤ 109) и r (1 ≤ r ≤ 109), задающих границы диапазона. Вторая
строка содержит количество элементов n
(1 ≤ n ≤ 18) в
наборе и сам набор чисел
a1, a2, ..., an . Каждое число в наборе лежит в пределах
от 1 до 109.
Выход. Для каждого теста в отдельной
строке выведите количество чисел из диапазона [l; r], которые
делятся хотя бы на одно число из набора a1, a2, ..., an.
|
Пример
входа |
Пример
выхода |
|
293 784 1 1 579000
987654 2 1 2 1 1000000000 2 2 3 |
492 408655 666666667 |
РЕШЕНИЕ
комбинаторика - принцип включения-исключения
Пусть a = { a1, a2,
..., an } – множество чисел.
Пусть numDivisible(l, r, a) – количество чисел от l до r
включительно, которые делятся хотя бы на одно из чисел a1, a2,
..., an. Воспользуемся
фактом, что
numDivisible(l, r, a) = numDivisible(1, r, a) –
numDivisible(1, l – 1, a).
Значение numDivisible(1, n, a) будем вычислять при
помощи функции f(n, a). Рассмотрим процесс вычисления
результата в зависимости от количества элементов в массиве a.
1. Если a содержит один элемент, то ответом
будет значение n / a[0] (округление до целого производится
вниз).
2. Пусть a содержит два элемента. Ответ будет
меньше n / a[0] + n / a[1], так как будут существовать числа,
которые делятся на a[0] и на a[1] одновременно. И в приведенной сумме
такие числа будут считаться дважды. Количество чисел, делящихся одновременно на
a[0] и на a[1], равно n / НОК(a[0], a[1]). Таким образом, для двух чисел
f(n, a)
= n / a[0] + n / a[1] –
n / НОК(a[0], a[1])
3. Пусть a содержит три элемента. Тогда согласно
принципу включения – исключения
f(n, a)
= n / a[0] + n / a[1] + n
/ a[2] –
– n / НОК(a[0], a[1]) – n /
НОК(a[1], a[2]) – n / НОК(a[0], a[2]) +
n / НОК(a[0], a[1], a[2])
Поскольку по
условию задачи массив a содержит от 1
до 18 элементов, то перебрать все подмножества множества a можно не более чем за 218 операций. При этом если
подмножество 
содержит нечетное
число элементов, то значение n / НОК(
) следует прибавлять к накапливаемой сумме (ответу), если
четное – то вычитать.
Если при
вычислении НОК() текущее значение НОК(
) станет больше n
для некоторого j < k, то процесс вычисления НОК() можно завершить, так как тогда n / НОК() = 0.
Реализация алгоритма
Функция f(n, a)
вычисляет значение numDivisible(1, n, a). Функция gcd вычисляет наибольший
общий делитель двух чисел.
int f(int N, int *a)
{
Ответ вычисляем в переменной res.
int res = 0;
Перебираем все подмножества множества { a1, a2, ..., an }. Переменная i содержит маску
подмножеств.
for(int i = 1; i <
(1<<n); i++)
{
В переменной lcm вычисляем НОК
подмножества, задаваемого маской i.
long long
lcm = 1;
В переменной bits подсчитываем
количество элементов в подмножестве, задаваемой маской i (число бит, равных 1, в i).
int bits = 0;
for(int j
= 0; j < n; j++)
if (i & (1 << j))
{
bits++;
int temp = gcd(lcm,a[j]);
lcm = lcm / temp * a[j];
Если НОК подмножества становится больше N, то далее
вычилять нет смысла. Все равно
значение N / lcm равно нулю.
if (lcm > N) break;
}
В зависимости от четности числа битов в маске (количества
элементов в текущем рассматриваемом подмножестве), прибавляем или вычитаем
очередное слагаемое.
if (bits % 2) res += N / lcm; else res -= N / lcm;
}
return res;
}
Основная часть
программы. Читаем входные данные.
while(scanf("%d %d",&l,&r)
== 2)
{
scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&a[i]);
Вычисляем искомое количество чисел на отрезке [l; r ].
res = f(r,a) - f(l - 1,a);
Выводим ответ.
printf("%d\n",res);
}